This invention relates to a method and apparatus for Cyclic Redundancy Check (will be termed "CRC" hereinafter) computation intended for data which is formed of a plurality of parallel bits, and particularly to a CRC computation method and apparatus suitable for the case where the number of parallel bits is varied.
There are known various methods for the computation of CRC used as an error detection character. One example is described in publication: IBM, TDM, Vol. 27, No. 6, November 1984, pp. 3572-3576. This method is categorized to be the CRC computation system in which data under test is subjected to bit-serial computation in accordance with a prescribed computation formula. The above publication presents the method of simultaneous parallel computation for a plurality of bits of data for accomplishing the same result as the case of bit-serial computation.
According to the above publication, for the state vector which represents a computation result up to the (n-1)th bit to be X(n), the input given at the (n)th bit to be u(n), and the computation result following the input to be X(n+1), a state transition matrix A (16-by-16 matrix for 16-bit data) and an input vector b(16-by-1 vector) are defined to meet: EQU X(n+1)=AX (n)+bu (n) (1)
When 8 bits are entered simultaneously (these 8 bits form an input vector u(n, 8)), then the computation is as follows. EQU X(n+8)=A.sup.8 X (n)+B.sub.8 u(n, 8) (2) EQU B.sub.8 =(A.sup.7 b A.sup.5 bb) (3)
Consequently, the same computation result X(n+8) as the case of bit-wise input for the 8 bits is achieved.
The foregoing known technique features that the state vector X(n) is the same as the result of serial computation for the input of n-1 bits and even if the n-1 bits are computed for an arbitrary m-bit set (8 bits in the above case), the unique state vector X(n) is produced so far as the matrices A.sup.m and B.sub.m are used.
In general, information processing systems such as computers deal with data in units of byte (8 bits) in most cases, and the application of the above-mentioned multiple bits simultaneous computation system readily realizes a high-speed computation circuit.
Conventionally, data is transferred between a CPU and an external storage in units of byte (8 bits), whereas recent demands of high-speed data transmission are often met by transferring 2 bytes (16 bits) or more simultaneously. The 1-byte transfer is used for a transfer rate of 3 Mbps, while the 2-byte transfer is for 6 Mbps. The number of bytes of simultaneous transfer may vary depending on the partner (CPU) in connection (i.e., static change). In addition, the number of bytes of simultaneous transfer may vary during the transfer depending on the number of bytes of transferred data, the transfer control mode and the data recording mode of the storage (i.e., dynamic change). An example of the dynamic change is that data in blocks of an odd number (2N+1) of bytes is transferred in 2-byte units in N cycles, which is followed by a cycle of 1-byte transfer. In order to assure the legitimacy of data transfer, CRC computation for transferred data is required.
However, the above-mentioned publication merely describes a general theory of CRC computation based on the m-bit parallel computation for accomplishing the same result as the bit-serial computation, and it does not deal with the simultaneous CRC computation useful for a data transfer system in which the number of bits or bytes of simultaneous transfer varies statically or dynamically.